package com.kevin.Code.Backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Vinlee Xiao
 * @Classname GenerateParentheses
 * @Description Leetcode 22 括号生成 中等难度 回溯算法
 * @Date 2021/9/27 17:14
 * @Version 1.0
 */
public class GenerateParentheses {


    List<String> result = new ArrayList<>();

    /**
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {

        char[] ch = new char[2 * n];
        int left = n;
        int right = n;
        Arrays.fill(ch, '.');

        backtrack(ch, n, left, right, 0);

        return result;
    }


    public void backtrack(char[] ch, int n, int left, int right, int index) {

        if (index == 2 * n) {
            result.add(new String(ch));
            return;
        }

        char[] tmp = new char[]{'(', ')'};

        for (int i = 0; i < 2; i++) {


            //什么情况跳过循环执行 相当于剪枝
            //右括号的数量小于左括号时跳过
            if (right < left || right < 0 || left < 0) {

                continue;
            }

            if (tmp[i] == '(' && left > 0) {
                left--;
                ch[index] = tmp[i];
                backtrack(ch, n, left, right, index + 1);
                ch[index] = '.';
                left++;
            } else if (tmp[i] == ')' && right > 0) {
                right--;
                ch[index] = tmp[i];
                backtrack(ch, n, left, right, index + 1);
                ch[index] = '.';
                right++;
            }
//
        }


    }

    public static void main(String[] args) {
        GenerateParentheses generateParentheses = new GenerateParentheses();

        List<String> stringList = generateParentheses.generateParenthesis(4);
        System.out.println(stringList.size());
        for (String s : stringList) {

            System.out.println(s);
        }
    }
}
